package com.some;

import java.util.Arrays;
public class ForthTopicTest {
	static int start= 0, end = 0,possible_start=0;   //弄两个值来存放最大子数组的开始、结束的索引
	public static void main(String[] args) {
		int[] a = { 13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12};   //初始化一个数组
		int[] max_arr = max_arr(a);
		System.out.println(Arrays.toString(max_arr));  //输出结果。
	}

	public static int[] max_arr(int[] array) {
		/*
		 * 最大子连续数组,其中算法复杂度为O(n^2),暴力破解。
		 */
		int max_sum = Integer.MIN_VALUE;		//最大值初始化
		for (int i = 0; i < array.length; i++) {
			int sum = array[i];
			for (int j = i ; j < array.length; j++) {
				if (sum > max_sum) {
					max_sum = sum;
					possible_start=i;						//最大子数组的开始位置的索引
					end= j;						//最大子数组的结束未知的索引
				}
				if(j<array.length-1){				
				sum += array[j+1];}
			}
		}
		start=possible_start;   
		if(end==start){System.out.println("没有最大连续子数组") ; return null;}
		int ans[] = new int[end- start + 1];
		for (int s = 0; s < ans.length; s++) {
			ans[s] = array[start++];
		}
		return ans;
	}
	}
